﻿#pragma once
#include "Index.h"

/**
* title: 字符串转换成整数(atoi).
* keys: 字符串
* https://leetcode.cn/problems/string-to-integer-atoi/
*
* 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:
* 1.若干空格
* 2.（可选）一个符号字符（'+' 或 '-'）
* 3. 数字，字母，符号，空格组成的字符串表达式
* 4. 若干空格
*
* 转换算法如下:
* 1.去掉无用的前导空格
* 2.第一个非空字符为+或者-号时，作为该整数的正负号，如果没有符号，默认为正数
* 3.判断整数的有效部分：
*  3.1 确定符号位之后，与之后面尽可能多的连续数字组合起来成为有效整数数字，如果没有有效的整数部分，那么直接返回0
*  3.2 将字符串前面的整数部分取出，后面可能会存在存在多余的字符(字母，符号，空格等)，这些字符可以被忽略，它们对于函数不应该造成影响
*  3.3  整数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。
*  具体来说，小于 −2^31的整数应该被调整为 −2^31 ，大于 2^31 − 1 的整数应该被调整为 2^31 − 1
* 4.去掉无用的后导空格
*
* 数据范围:
* 1.0 <=字符串长度<= 100
* 2.字符串由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
*/
namespace ParseStringToInt
{
	class Question {
	public:
		virtual int myAtoi(std::string str)=0;
	};

	class Solution:public Question
	{
	public:
		int myAtoi(std::string s) override
		{
			if (s.empty())
				return 0;

			const int s_size = s.size();
			int num = 0;
			int sign = 1;
			bool is_parsing = false;
			for (int i = 0; i < s_size; ++i)
			{
				const char& ch = s[i];
				if (!is_parsing)
				{
					if (ch == ' ')
						continue;
					else if (ch == '-')
					{
						sign = -1;
						is_parsing = true;
					}
					else if (ch == '+')
					{
						is_parsing = true;
					}
					else if (ch >= '0' && ch <= '9')
					{
						is_parsing = true;
						num = ch - '0';
					}
					else
						break;
				}
				else
				{
					if (ch >= '0' && ch <= '9')
					{
						static constexpr int PRE_INT_MAX = INT_MAX / 10;
						static constexpr int MOD_INT_MAX = INT_MAX % 10;
						static constexpr int PRE_INT_MIN = INT_MIN / 10;
						static constexpr int MOD_INT_MIN = -(INT_MIN % 10);
						//检查越界
						if (num > PRE_INT_MAX || (num == PRE_INT_MAX && (ch - '0') > MOD_INT_MAX))
							return INT_MAX;
						if (num < PRE_INT_MIN || (num == PRE_INT_MIN && (ch - '0')>MOD_INT_MIN))
							return INT_MIN;
						//累加数位
						num = num * 10 + sign * (ch - '0');
					}
					else
						break;
				}
			}

			return num;
		}
	};

	class LowHighRange:public Question
	{
	public:
        int myAtoi(std::string s) override
        {
            if (s.empty())
                return 0;
            const int sSize = s.size();

            bool negative = false;
            int ansHigh = 0;
            int ansLow = 0;

            int index = 0;
            //忽略前面的0
            while (index < sSize && s[index] == ' ')
                index++;
            //取出符号位
            if (index < sSize)
            {
                switch(s[index])
                {
                case '-':
                    negative = true;
                    index++;
                    break;
                case '+':
                    negative = false;
                    index++;
                    break;
                }
            }

            long long nums=0;
            //取出数字部分
            while (index < sSize && s[index] >= '0' && s[index] <= '9')
            {
                ansHigh *= 10;
                ansLow *= 10;

                ansLow += s[index] - '0';
                nums = nums * 10 + (s[index] - '0');

                if (ansLow > LOW)
                {
                    ansHigh += (ansLow >> 16);
                    ansLow &= 0x0000ffff;
                }

                if (isOverflow(ansHigh, ansLow, negative))
                    return negative ? INT_MIN : INT_MAX;

                index++;
            }

            if (negative)
            {
                ansHigh = -ansHigh;
                ansLow = -ansLow;
            }

            return ansHigh*(1<<16) + ansLow;
        }
    private:
        bool isOverflow(int high, int low, bool negative)
        {
            if (!negative)
                return !(high <= HIGH && low <= LOW);
            else
                return !(high <= HIGH && low <= LOW + 1);
        }
    private:
        const int LOW = INT_MAX & 0xffff;
        const int HIGH = (INT_MAX & 0xffff0000) >> 16;
	};

	class Practice:public Question
	{
	public:
		int myAtoi(std::string str) override
		{
			if(str.empty())
				return 0;

			const int str_size=str.size();
			//忽略前导空格
			std::size_t start_pos= str.find_first_not_of(' ');
			if(start_pos==std::string::npos || start_pos>=str_size)
				return 0;

			//读出符号位
			int num_sign=1;
			if(str[start_pos]=='+' || str[start_pos]=='-')
			{
				num_sign=str[start_pos]=='-'?-1:1;
				start_pos++;
			}

			//读出数值位
			long long num_val=0;
			for(int i=start_pos;i<str_size;++i)
			{
				const char& ch=str[i];
				if(ch >= '0' && ch <='9')//是数字字符
				{
					if(num_val==0)
						num_val= ch - '0';
					else
						num_val=num_val*10 + (ch - '0');

					//判断是否超int数值上限范围
					if(num_sign>0 && num_val*num_sign > INT_MAX)
						return INT_MAX;
					else if(num_sign<0 && num_val*num_sign < INT_MIN)
						return INT_MIN;
				}
				else
				{
					//当遇到非数字字符时,后面的字符串内容就不再解析了
					break;
				}
			}

			return num_sign * num_val;
		}
	};

	TEST(ParseStringToIntTest, parseStrToInt)
	{
		std::unordered_map<std::string, int> testSamples;
		testSamples["82"] = 82;
		testSamples["   -12    "] = -12;
		testSamples["4396 clearlove"] = 4396;
		testSamples["clearlove 4396"] = 0;
		testSamples["-987654321111"] = INT_MIN;
		testSamples["-99999999999999999999999999999"] = INT_MIN;
		testSamples["99999999999999999999999999999"] = INT_MAX;
		testSamples["+9321111"] = 9321111;
		testSamples["+932.321.421321"] = 932;
		testSamples["93221.421321"] = 93221;

		TEST_SOLUTION3(Question, Solution, LowHighRange,Practice, &)
		{
			for (auto& kvp : testSamples)
			{
				ASSERT_EQ(solution->myAtoi(kvp.first), kvp.second)
					<< "numStr=" << kvp.first;
			}
		};
	}
}